/*
 * Heap.java
 *
 * Created on June 6, 2006, 8:59 AM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package shortestpath;

/**
 *
 * @author hai
 */
public class Heap {
   
    int hole;
    Node[] ar=new Node[20];
    
    public Heap(){
        hole=0;       
    }
    
    public void insert(Node i){
        int temp=hole;
        while (hole!=0 && parent(hole).getCost()>i.getCost()){
           
            ar[hole]=parent(hole);
            hole=(hole-1)/2;
            
        }
        if (hole==0) ar[0]=i;
        else ar[hole]=i;
        hole=temp+1;
        
    }
    public Node deleteLeast(){
        int i=0;
        Node temp=ar[0];
        for(;;){
            if (hasNoChild(i)){
                ar[i]=ar[hole-1];
                hole--;
                break;
            }
            if (hasOneChild(i)){
                ar[i]=ar[hole-1];
                hole--;
                break;
            }
            if (hasTwoChildren(i)){
                int min;
                if (ar[i*2+1].getCost()<ar[i*2+2].getCost()) min=i*2+1;
                else min=i*2+2;
                if (ar[min].getCost()>ar[hole-1].getCost()){
                    ar[i]=ar[hole-1];
                    hole--;
                    break;
                }
                else{
                    ar[i]=ar[min];
                    i=min;
                }
                
            }
                
        }
        return temp;
    }
    public void restructure(int nodeId){
        Node[] temp=new Node[20];
        int index=0;
        Node cur;
        do{
            cur=this.deleteLeast();            
            temp[index]=cur;
            index++;   
        
        }while(cur.id!=nodeId);
        for (int i=0; i<index; i++){
            insert(temp[i]);
        }            
        
    }
    public boolean isEmpty(){
        return hole==0;
    }
    
    public boolean hasTwoChildren(int index){
        return (hole>index*2+2);
        
    }
    public boolean hasNoChild(int index){
        return (hole<=index*2+1);
    }
    public boolean hasOneChild(int index){
        return (!hasTwoChildren(index)&&!hasNoChild(index));
    }
    public Node parent(int hole){
        return ar[(hole-1)/2];
    }
}
class Node{
    int id;
    private int cost;
    public Node parent;
    public Node(int id){
        this.id=id;
    }
    
    public Node(int id, int cost){
        this.id=id;
        this.cost=cost;
    }
    public void setCost(int value) {
        cost=value;
    }
    public int getCost(){
        return cost;
    }
    public void changeCost(int value) throws NodeValueChangeException{
        cost=value;
        throw new NodeValueChangeException(this.id, value);
        
        
    }
    

}
class NodeValueChangeException extends Exception{
    int newValue;
    int id;
    public NodeValueChangeException(int id, int value){
        this.id=id;
        newValue=value;
}

}

